package org.tomdayu.algo;

/**
 * 二分查找 使用前提：数组有序
 *
 */
public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {1,3,3,3,3,4,5};
        System.out.println(binarySearch(arr,0, 3, 2));//
    }

    /**
     * 死循环案例
     * @param arr
     * @param left
     * @param right
     * @param findval
     * @return
     */
    public static int binarySearch(int[] arr, int left, int right, int findval) {
        //因为每次递归，若不满足条件，要么就是左指针后移要么就是右指针左移。当两个指针移动到相同的元素时候，如果依然不满足条件，那么区间未找到元素。
        //左指针后移或者右指针左移，此时，left往后或者right往前，因此left>right就是判断没有找到元素的条件。
        //如果没有找到，要求找到第一个比它大的元素
        //思路：没找到，那么一定有left=right的情况，这趟循环
//        if (left > right) return -1;
        if (left > right) {
            //找到比findval大的元素
            return arr[left] > findval ? left : left+1;
        }

        int mid = (left + right) / 2;
        if (findval > arr[mid]) {
            return binarySearch(arr, mid + 1, right, findval);
        } else if (findval < arr[mid]) {
            return binarySearch(arr, left ,mid - 1, findval);
        } else {
            return mid;
        }
    }
}
